Kademlia

标签

分布式/P2P 与路由

字数

6668 字

阅读时间

26 分钟

Kademlia（IPTPS 2002）是这批的最后一篇，也是最短、机制最统一的一篇。它的做法是把"距离"这一个选择换掉 —— 距离就是两个标识符按位异或（XOR）后的整数值 —— 然后路由表结构、查找的并行性、以及"在线越久越可信"这三件事都能从这一个选择里推出来。

它的三条"第一"：

凭借基于 XOR 的度量拓扑，Kademlia 是第一个把可证明的一致性与性能、最小化延迟的路由、以及对称且单向的拓扑结合起来的 P2P 系统。 它引入了并发参数 $\alpha$，让人可以用一个常数倍的带宽换取异步的最低延迟选择跳与无延迟的故障恢复。最后，Kademlia 是第一个利用"节点失败率与在线时长成反比"这一事实的 P2P 系统。

先看清 Chord / Pastry 差在哪

它明确指出了前作的机制缺陷，而这些批评正好是 XOR 要解决的：

Chord 的节点不会从收到的查询里学到有用的路由信息。更糟的是，不对称性导致路由表变得僵硬。 Chord 节点 finger table 的每一项必须存"某个区间之前的那一个精确节点"。任何真正落在这个区间内的节点，都会因为不够靠近区间之前的那些节点而不能用。

Kademlia 相反，可以把查询发给"某个区间内的任意节点"，从而让它能基于延迟选路，甚至向若干个同样合适的节点并行、异步地发查询。

第二条批评指向的是它自己那条线的前作：

在已有系统里，Kademlia 最接近 Pastry 的第一阶段 —— 那个阶段（虽然该文没有这样描述）按 Kademlia 的 XOR 度量连续找到距目标 ID 大约一半远的节点。然而在第二阶段，Pastry 把度量换成了 ID 之间的数值差，复制时也用第二套数值差度量。不幸的是，按第二套度量接近的节点按第一套度量可能相当远，这会在特定的节点 ID 值处产生不连续，降低性能，并使最坏情况行为的形式化分析复杂化。

还有一条贯穿全篇的机制对比：Kademlia 从开始到结束只用一个路由算法，而其他系统用一个算法靠近目标、再用另一个算法走最后几跳。

二进制树视角与 XOR 的三条性质

Kademlia 事实上把节点看作一棵二叉树上的叶子，每个节点的位置由它 ID 的最短唯一前缀决定。 对任一节点，把这棵二叉树分成一串逐级更低的、不包含该节点的子树：最高的子树是"不含该节点的、二叉树的那一半"，下一个是"剩下的树里不含该节点的、那一半"，依此类推。例子里节点 0011 对应的子树前缀是 1、01、000、0010。

协议要保证的性质是：每个节点在它的每一棵子树里都至少知道一个节点（只要那棵子树里有节点）。 有了这条保证，任何节点都能按 ID 定位任何其他节点 —— 查找就是在这串子树里逐级往下走。

距离的定义只有一行：给定两个 160 位标识符 $x$ 与 $y$，

$$d(x,y)=x\oplus y(\text{按位异或，再解释为整数})$$

接着三条性质，每一条都立刻被用上：

性质	内容	用途
度量合法性	$d(x,x)=0$；$x\ne y$ 时 $d(x,y)>0$；$d(x,y)=d(y,x)$	是个（非欧氏的）度量
三角不等式	$d(x,y)+d(y,z)\ge d(x,z)$	由 $d(x,y)\oplus d(y,z)=d(x,z)$ 及 $\mathrm{\forall }a,b\ge 0:a+b\ge a\oplus b$ 推出
单向性	对任一点 $x$ 与任一距离 $\mathrm{\Delta }>0$，恰好存在一个点 $y$ 使 $d(x,y)=\mathrm{\Delta }$	所有对同一个 key 的查找，无论从哪个节点发起，都沿同一条路径收敛

单向性那一条的用处很具体：正因为查找路径唯一，沿查找路径缓存 (key,value) 就能缓解热点。这一点在后面的缓存设计里直接兑现了。

还有一条对称性值得单独记，因为它和单向性是两件事："像 Pastry 而不像 Chord，XOR 拓扑还是对称的"（$d(x,y)=d(y,x)$ 对所有 $x,y$）。对称性在哪里付账在证明里点明了：因为对称，一个节点在收发请求过程中与之通信的那些节点的 ID，其分布恰好与该节点的 bucket 区间相合 —— 于是每一个收发请求都会顺带更新节点的 bucket，使得"bucket 里的节点同时失效"这一坏情形的实际概率远小于按时间算出来的概率。

XOR 与二叉树的关系：在一棵满的 160 位 ID 二叉树里，两个 ID 之间距离的大小就是包含它们的最小子树的高度；树不满时，离 ID $x$ 最近的叶子是与 $x$ 共享最长公共前缀的那个；若有空分支，离 $x$ 最近的叶子等于"把 $x$ 中对应空分支的位翻转后所得 ID 的最近叶子" —— 这句话在证明一节里被用来处理 bucket 为空时的收敛。

k-bucket 与「在线越久越可信」

节点的路由状态叫 k-bucket：对每个 $0\le i<160$，维护一张 (IP 地址, UDP 端口, Node ID) 三元组的列表，收录的都是"与自己的距离介于 $2^i$ 与 $2^{i+1}$ 之间"的节点。 每张 k-bucket 按最后一次见到的时间排序 —— 最久没见到的在头部、最近见到的在尾部。$i$ 小的时候 bucket 通常是空的（不存在合适的节点）；$i$ 大时列表可以长到 $k$ 项，$k$ 是一个系统级复制参数，取法要使得"任意给定的 $k$ 个节点在一个小时内相继失败"极不可能（例如 $k=20$）。

收到任何消息（请求或应答）时的更新规则是这套设计里最值得逐字读的一段：

1. 若发送者已在对应 bucket 里 → 把它移到尾部；
2. 若不在、且 bucket 未满 → 把新发送者插到尾部；
3. 若 bucket 已满 → ping 该 bucket 里最久没见到的那个节点：
   • 它不应答 → 把它逐出，新发送者插到尾部；
   • 它应答了 → 把它移到尾部，新发送者的联系信息被丢弃。

k-bucket 实际上实现的是一种"最久未见者优先逐出"策略，但有个例外：活着的节点永远不会被移出列表。

这条"偏向老联系人"的规则不是猜的，动机来自 Saroiu 等人采集的 Gnutella 跟踪数据：一个节点已经在线越久，它在下一个小时里继续在线的概率就越高。通过留住最老的活联系人，k-bucket 最大化了它所含节点保持在线这一事件的概率。

附带还有一个安全收益：k-bucket 提供对某些 DoS 攻击的抵抗 —— 你无法通过向系统灌入大量新节点来冲掉节点的路由状态，因为 Kademlia 只会在老节点离开时才插入新节点。

四个 RPC 与 node lookup

协议只有四个 RPC：ping（探活）、store（让某个节点存一个 key,value）、find_node（给一个 160 位 ID，返回它知道的最接近该 ID 的 $k$ 个节点的三元组，可以来自单个 bucket、也可以在最近的 bucket 未满时来自多个 bucket）、find_value（行为与 find_node 相同，唯一区别是：若接收方存过这个 key 的值，就直接把值返回）。

一条安全细节：所有 RPC 的接收方都必须回显一个 160 位随机 RPC ID，这对地址伪造提供了一定抵抗；ping 也可以搭在 RPC 应答上捎带，让接收方多一层对发送方网络地址的确信。

node lookup 是最重要的过程（定位距某 ID 最近的 $k$ 个节点），用的是递归算法：

1. 发起者从自己最近的非空 k-bucket 里挑 $\alpha$ 个节点（若该 bucket 不足 $\alpha$ 项，就取它知道的最接近的 $\alpha$ 个）；
2. 向这 $\alpha$ 个节点并行、异步地发 find_node。$\alpha$ 是系统级并发参数，例如 3。
3. 递归步：发起者把 find_node 重发给从先前 RPC 里学到的节点 —— 这个递归可以在上一轮 $\alpha$ 个 RPC 还没全部返回时就开始。在它听说过的、离目标最近的 $k$ 个节点里，挑 $\alpha$ 个尚未查询过的重发；
4. 应答慢的节点被移出考虑范围，直到（如果）它们应答为止；
5. 若某一轮 find_node 没能返回比已见过的最接近者更近的节点，发起者就把 find_node 重发给"它尚未查询过的那 $k$ 个最近节点" —— 这是防止局部停滞的放宽手段；
6. 查找在发起者已从它见过的最接近的 $k$ 个节点都查询并得到应答时终止。

$\alpha$ 取值的意义：$\alpha =1$ 时，查找算法在消息开销与检测失败节点的延迟上与 Chord 相似。但 Kademlia 能以更低延迟完成路由，因为它可以在这 $k$ 个节点里任选一个来转发请求。

脚注里还有一句很实用的话：bucket 项与 find 的应答都可以附上往返时间估计，用来挑选那 $\alpha$ 个节点。

路由表：一棵按需生长的二叉树

路由表就是一棵二叉树，叶子是 k-bucket。每个 k-bucket 里的节点共享 ID 的某个前缀，那个前缀就是它在二叉树中的位置 —— 于是每个 bucket 覆盖 ID 空间的一段，合起来无缝地覆盖整个 160 位空间。树上的节点按需动态分配：

• 初始时路由树只有一个节点 —— 一张覆盖整个 ID 空间的 k-bucket；
• 学到新联系人时插到合适的 bucket：未满就直接插；
• 已满、且该 bucket 的范围包含本节点自己的 ID → 把 bucket 一分为二，旧内容分到两边，重试插入；
• 已满、但范围不含本节点自己的 ID → 新联系人直接被丢弃。

不平衡树那个微妙处

这是 Kademlia 常被讲漏的一点。一个例子很具体：假设节点 $u$ 加入系统，是唯一一个 ID 以 000 开头的节点；再假设系统里已经有超过 $k$ 个以 001 开头的节点。

那么每个以 001 开头的节点都会有一张空 k-bucket，$u$ 本该被插进去，然而 $u$ 的 bucket 刷新只会通知到其中 $k$ 个。

解法是：Kademlia 节点会保留某个规模至少为 $k$ 的子树里的所有有效联系人，即便这需要分裂那些"本节点自己的 ID 并不在其中"的 bucket。 当 $u$ 刷新区分出来的那些 bucket 时，所有以 001 开头的节点都会得知它的存在。这些额外的分裂在路由树的分支上造成的是一点期望常数的规则性破坏。

存储、重发布与缓存

存：定位距 key 最近的 $k$ 个节点，向它们发 store。

重发布：为保证持久性，节点必须周期性重发布。有两种现象会导致有效 key 查不到：① 最初存下 (key,value) 的那 $k$ 个节点里有些离开了；② 有新节点以更接近该 key 的 ID 加入。于是 Kademlia 每小时重发布每个 (key,value) 一次。

朴素实现下，存有该 (key,value) 的最多 $k$ 个节点每个都要每小时做一次 node lookup 加 $k-1$ 次 store。两条优化把它压了下来：

1. 收到某个 (key,value) 的 store 时，接收方就假定这条 RPC 也发给了另外 $k-1$ 个最近的节点，于是它在下一个小时内不再重发布它 → 只要各节点的重发布间隔不是精确同步的，每小时就只有同一个 (key,value) 的一个节点在重发布；
2. 省掉重发布之前的 node lookup：为处理不平衡树，节点会按需分裂 bucket，以保证自己完整知道一个规模至少为 $k$ 的周围子树。只要在重发布前刷新这棵子树里的所有 k-bucket，它就能自己算出任意 key 的 $k$ 个最近节点，而且这些 bucket 刷新还能摊到许多 key 的重发布上。这为什么成立可以用两种情况论证（key 落在子树范围内 / key 落在子树外但 $u$ 本身是最近 $k$ 个之一）。

新节点加入时要存它该存的那份：已有节点因为完整知道自己的周围子树，所以知道新节点应当存哪些 (key,value)；于是任何得知新节点的节点会发 store 把相关数据转过去。为避免重复的 store，一个节点只在"自己的 ID 比别的节点更接近该 key"时才转这份数据。

缓存这一步把单向性直接用上了：一次查找成功后，发起者把 (key,value) 存在它观察到的、离该 key 最近但并没有返回该值的那个节点上。

由于拓扑的单向性，对同一个 key 的后续查找很可能会在到达最近的节点之前先命中缓存。

为防止"过度缓存"，有一个很精巧的做法：

把任意节点里一个 (key,value) 的过期时间，设为与"当前节点到 ID 最接近该 key 的那个节点之间的节点数"成指数反比。（脚注补充：这个数目可以从当前节点的 bucket 结构推断出来。）

为什么不用 LRU：简单的 LRU 逐出会给出相似的生存期分布，但缓存大小没有任何自然的取法，因为节点事先并不知道系统会存多少值。

刷新：bucket 通常靠过路流量保持新鲜；为处理"某段 ID 范围没有查找"的病态情形，每个节点会刷新任何它过去一小时内没做过 node lookup 的 bucket —— 刷新就是"在该 bucket 的范围里挑一个随机 ID 做一次节点搜索"。

加入

节点 $u$ 必须先有一个已在系统中的节点 $w$ 的联系方式，然后三步：① 把 $w$ 插进合适的 k-bucket；② 对自己的 node ID 做一次 node lookup；③ 刷新所有比它最近的邻居更远的 k-bucket。 刷新过程中 $u$ 既填充自己的 bucket，也按需把自己插进别的节点的 bucket。

实现里两条值得记的优化

一、推迟探测，用 replacement cache。 按描述，只要从 bucket 范围内某个未知节点收到消息而 bucket 已满，就要发一次 ping —— 那会产生大量网络消息。实现改法是：把新联系人放进一个"候选替换缓存"，等下次真的要查询该 bucket 里的联系人时，再把不应答的逐出、用候选缓存里的条目补上。候选缓存同样按最后见到时间排序，最近见到的替换优先级最高。

配套的两条因为 UDP 而来的处理：丢包常常意味着网络拥塞，所以 Kademlia 会锁住不应答的联系人，并在一个指数增长的退避区间内不再给它发 RPC；而且因为在多数阶段查找只需从 $k$ 个节点里听到一个，系统通常不会把丢掉的 RPC 重传给同一个节点。一个联系人连续 5 次 RPC 不应答才算 stale；若某个 bucket 未满或它的候选缓存为空，Kademlia 只是"标记"stale 而不移除 —— 这条保证的是：如果一个节点自己的网络连接临时中断，它不会把自己的 k-bucket 全部清空。

二、一次看 $b$ 位来减少跳数。 默认一眼看 1 位，期望跳数是 ${\log }_{2}n$；把路由表扩大到期望 $2^b{\log }_{2^b}n$ 张 k-bucket，期望跳数就降到 ${\log }_{2^b}n$。实现上除了"范围含自身 ID"那种分裂，还会对不含自身 ID 的范围也分裂，最多 $b-1$ 层：通用规则是 当 bucket 范围含本节点 ID、或该 bucket 在路由树中的深度 $d$ 满足 $d\equiv 0(\mathrm{mod}b)$ 时分裂一个已满的 k-bucket（深度就是该 bucket 范围里所有节点共享的前缀长度）。当前实现用 $b=5$。

这里有一个很关键的技术论断，说明 XOR 为什么让 $b>1$ 变得干净：

虽然基于 XOR 的路由和 Pastry、Tapestry 与 Plaxton 的分布式搜索算法的第一阶段相似，但这三者在推广到 $b>1$ 时都变得更复杂。没有 XOR 拓扑，就需要一个额外的算法结构来在"共享同一前缀但下一位 $b$-bit 数字不同"的那些节点中发现目标。三者各自用不同方式解决，各有缺点；它们都需要在大小为 $O(2^b{\log }_{2^b}n)$ 的主表之外再加大小为 $O(2^b)$ 的次级路由表。这增加了自举与维护成本、使协议复杂化，而且对 Pastry 与 Tapestry 来说，还使正确性与一致性的形式化分析变得复杂或被阻断了。Plaxton 有证明，但该系统对 P2P 这种高度易故障的环境针对性更弱。

证明要点

要证的是多数操作耗时 $\log n+c$（$c$ 是小常数），且一次 key,value 查找以压倒性概率返回系统里存着的 key。几个定义先立起来：

• 覆盖距离区间 $[2^i,2^{i+1})$ 的 k-bucket，索引为 $i$；
• 一个节点的深度 $h=160-i$，其中 $i$ 是非空 bucket 的最小索引；
• 节点 $y$ 在节点 $x$ 中的 bucket 高度 = （$x$ 会插入 $y$ 的 bucket 的索引）−（$x$ 中最不重要的空 bucket 的索引）。

因为 ID 是随机选的，严重不均匀的分布不太可能出现，于是任何给定节点的深度以压倒性概率在一个常数与 $\log n$ 之间；第 $k$ 近节点里最接近某 ID 的那个节点的 bucket 高度，很可能在一个常数与 $\log k$ 之间。

在"每个 bucket 只要有节点存在就至少含一个联系人"这条不变量下：设距目标最近的节点深度为 $h$。若它最重要的 $h$ 张 bucket 都非空，查找过程每步都会找到一个近一半（距离少一位）的节点，于是在 $h-\log k$ 步内找到目标。 若某张 bucket 是空的，最后几步就不会把距离减半 —— 但搜索会表现得完全像是"把 key 里对应那张空 bucket 的位翻转了"一样继续（这正好接上前面对空分支的定义）。所以查找总是在 $h-\log k$ 步内返回最近的节点。而且一旦找到最近的节点，并发度会从 $\alpha$ 切换到 $k$；找剩下 $k-1$ 个节点所需步数不超过"第 $k$ 近节点里最接近者的 bucket 高度"，不太可能超过一个常数加 $\log k$。

不变量的维持：刷新之后，一张 bucket 要么含 $k$ 个有效节点、要么含它范围内的每一个节点（如果不足 $k$ 个）。新加入的节点也会被插进任何未满的 bucket。所以

破坏不变量的唯一方式，是某张 bucket 的范围里存在 $k+1$ 个或更多节点、而 bucket 里实际含有的那 $k$ 个在没有任何中间查找或刷新的情况下全部失败。 而 $k$ 正是按"一小时内（最大刷新时间）同时失败的概率很小"来选的。

实际概率比按时间算出来的更小，理由是前面提过的对称性（收发请求都在更新 bucket）。另外两条兜底：即使某张 bucket 的不变量真的破了，也只影响运行时间（给某些查找加一跳），不影响 node lookup 的正确性；要让一次查找失败，路径上的 $k$ 个节点必须各自在同一张 bucket 里丢掉 $k$ 个节点且中间没有任何查找或刷新 —— 若这些节点的 bucket 互不重叠，这件事的概率是 $2^{-k^2}$（若重叠，则出现在多个节点 bucket 里的节点很可能在线更久、失败概率更低）。

(key,value) 的恢复：发布时落在 $k$ 个最近的节点上，且每小时重发布。因为即便最不可靠的新节点也有 $1/2$ 的概率撑过一个小时，一小时后这份 (key,value) 仍存在于"最接近该 key 的那 $k$ 个节点之一"上的概率是 $1-2^{-k}$。

边界也很清楚：若某个 key 的 $k$ 个最近节点全部失败、而这份 (key,value) 又没在别处被缓存，Kademlia 就会存不住它、从而丢掉这个 key。

与前几篇的关系

对 Chord —— Chord 的 finger table 每一项必须是一个精确节点（区间之前的那一个），而 Kademlia 可以选区间内任意节点，于是 Kademlia 能基于延迟选路、能并行发查询，而 Chord 的路由表是"僵硬"的。另一处差异在方向：Chord 用环上的顺时针距离（不对称），XOR 既单向又对称。Chord 的节点不会从收到的查询里学到路由信息，而 Kademlia 因为对称性每次收发都在更新 bucket。

对 Pastry —— Kademlia 最像 Pastry 的第一阶段（按 XOR 度量连续把距离减半），但 Pastry 在第二阶段换成了数值差度量，并在复制时也用它；而两套度量之间的不连续会在特定 ID 值处伤害性能、并使最坏情况分析复杂化。而 Kademlia 从开始到结束只用一个度量、一个算法。另一处对比在 $b>1$ 的推广上（见上一节）：Pastry 需要额外的次级路由表（$O(2^b)$）与更复杂的协议。

对 CAN —— CAN 用几何坐标空间里的直线，Kademlia 用二进制树；两者的共同点是路由决策完全由 ID 决定、不需要按名称查表，区别在 CAN 要维持几何邻居关系而 Kademlia 的 bucket 是按距离区间分层维护、且能容忍区间内任选。

相关

• Pastry —— 关联最紧的一篇：Kademlia 最像 Pastry 的第一阶段，而 Pastry 的第二阶段换度量正是 Kademlia 批评的那个设计点（不连续 / 分析复杂）。另一处是 $b>1$ 推广时 Pastry 需要额外次级表
• Chord —— 另一处亲口对照：Chord 的 finger 项必须是精确的"区间前一个节点" → 路由表僵硬、不能并行发查询；且 Chord 节点不会从查询中学到路由信息。两者都用 160 位 ID 与 $O(\log N)$ 状态，但度量选择（数值差 vs XOR）决定了能否"区间内任选"
• CAN —— 第四种"位置算得出来"的路线；CAN 靠几何坐标与邻居关系，Kademlia 靠 XOR 与 bucket 区间
• 一致性哈希算法 —— 本专栏的前置工具。注意 Kademlia 的 node ID "目前只是随机 160 位标识符，不过也可以像 Chord 那样构造" —— 它并不依赖环，所以不需要虚拟节点那种"为均匀性打补丁"的机制，均匀性由随机 ID 与 bucket 分裂规则自然保证
• Dynamo —— 同样用"随机 ID + 就近"的思路，但 Dynamo 用环 + 虚拟节点 + 偏好列表，Kademlia 用二叉树 + bucket + 后缀缓存；两者都在处理"相邻 ID 的节点在地理上分散"这个由随机分配带来的后果，手段完全不同
• Ceph —— CRUSH 与 Kademlia 都属"纯函数式的位置计算"，但 CRUSH 需要一张分层的 cluster map 来描述故障域，而 Kademlia 的 bucket 结构本身就是 map、且由协议自动生长

参考

• P. Maymounkov, D. Mazières. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric. IPTPS 2002, LNCS 2429.

贡献者

YJ

文件历史

最后编辑于 5 分钟前查看完整历史

7864e-111

ae1ee-docs：内容完善

448f1-分布式